package com.itheima.algorithm.binarysearchtree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: TylerZhong
 * @description:
 */
public class BSTTree1 {

    public BSTNode root;

    public static class BSTNode {
        public int key;
        public Object value;
        public BSTNode left;
        public BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public BSTTree1() {
    }

    public BSTTree1(BSTNode root) {
        this.root = root;
    }

    /*public Object get(int key) {
        return doGet(root, key);
    }

    private Object doGet(BSTNode node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            return doGet(node.left, key);
        } else if (key > node.key) {
            return doGet(node.right, key);
        } else {
            return node.value;
        }
    }*/

/*    public Object min() {
        return doMin(root);
    }*/

    public Object max() {
        return max(root);
    }

    public Object max(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    /**
     * 查找最小关键字对应值
     * @return
     */
    public Object min() {
        return min(root);
    }

    /**
     * 查找最小关键字对应值
     * @return
     */
    public Object min(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    public Object doMin(BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.value;
        }
        return doMin(node.left);
    }

    public Object get(int key) {
        BSTNode node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }

    public void put(int key, Object value) {
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            parent = node;
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                node.value = value;
                return;
            }
        }
        BSTNode bstNode = new BSTNode(key, value);
        if (parent == null) {
            root = bstNode;
            return;
        }
        if (key < parent.key) {
            parent.left = bstNode;
        } else {
            parent.right = bstNode;
        }
    }

    /**
     * 查找关键字的前任值
     * @param key - 关键字
     * @return 前任者
     */
    public Object predecessor(int key) {
        BSTNode p = root;
        BSTNode ancestorFromLeft = null;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (key > p.key) {
                ancestorFromLeft = p;
                p = p.right;
            } else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        // 找到节点  情况1：节点没有左子树，此时前任是左子树的最大值
        if (p.left != null) {
            return max(p.left);
        }
        // 找到节点  情况2：节点没有左子树，若离它最近的，自左而来的祖先就是前任
        return ancestorFromLeft != null ? ancestorFromLeft.value:null;
    }

    /**
     * 查找关键字的后任值
     * @param key - 关键字
     * @return 后任者
     */
    public Object successor(int key) {
        BSTNode p = root;
        BSTNode ancestorFromRight = null;
        while (p != null) {
            if (key < p.key) {
                ancestorFromRight = p;
                p = p.left;
            } else if (key > p.key) {
                p = p.right;
            } else {
                break;
            }
        }
        // 没找到节点
        if (p == null) {
            return null;
        }
        // 找到节点  情况1：节点没有右子树，此时后任是右子树的最小值
        if (p.right != null) {
            return min(p.right);
        }
        // 找到节点  情况2：节点没有右子树，若离它最近的，自右而来的祖先就是后任
        return ancestorFromRight != null ? ancestorFromRight.value:null;
    }

    /*public Object delete(int key) {
        BSTNode p = root;
        BSTNode parent = null;
        while (p != null) {
            if (key < p.key) {
                parent = p;
                p = p.left;
            } else if (key > p.key) {
                parent = p;
                p = p.right;
            } else {
                break;
            }
        }

        if (p == null) {
            return null;
        }
        // 删除操作
        if (p.right == null) {
            // 情况1
            shift(parent, p, p.left);
        } else if (p.left == null) {
            // 情况2
            shift(parent, p, p.right);
        } else {
            // 情况4
            // 4.1 被删除节点找后继
            BSTNode s = p.right;
            BSTNode sParent = p; // 后继父亲
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            // 后续节点即为 s
            if (sParent != p) { // 不相邻节点
                // 4.2 删除和后继不相邻，处理后继的后事
                shift(sParent, s, s.right); // 不可能有左孩子
                s.right = p.right;
            }
            // 相邻节点
            // 4.3 后继取代被删除节点
            shift(parent, p, s);
            s.left = p.left;
        }
        return p.value;
    }*/

    /**
     *  托孤方法
     * @param parent - 被删除节点的父亲
     * @param deleted - 被删除节点
     * @param child - 被顶上去的节点
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            root = child;
        } else if (parent.left == deleted) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    public Object delete(int key) {
        List<Object> list = new ArrayList<>();
        root = doDelete(root, key, list);
        return list.isEmpty() ? null : list.get(0);
    }

    public BSTNode doDelete(BSTNode node, int key, List<Object> list) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = doDelete(node.left, key, list);
            return node;
        }
        if (key > node.key) {
            node.right = doDelete(node.right, key, list);
            return node;
        }

        list.add(node.value);

        // 情况1 - 只有右孩子
        if (node.left == null) {
            return node.right;
        }
        // 情况2 - 只有左孩子
        if (node.right == null) {
            return node.left;
        }
        // 情况3 - 有两个孩子
        BSTNode s = node.right;
        while (s.left != null) {
            s = s.left;
        }
        s.right = doDelete(node.right, s.key, new ArrayList<>());
        s.left = node.left;
        return s;
    }

    // 找 < key 的所有 value
    public List<Object> less(int key) {
        ArrayList<Object> result = new ArrayList<>();
        LinkedList<BSTNode> stack = new LinkedList<>();
        BSTNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key < key) {
                    result.add(pop.value);
                } else {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }

    // 找 > key 的所有 value
    /*public List<Object> greater(int key) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }
                p = pop.right;
            }
        }
        return result;
    }*/

    // 找 > key 的所有 value
    public List<Object> greater(int key) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.right;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key > key) {
                    // 处理值
                    result.add(pop.value);
                } else {
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }

    // 找 >= key1 || <= key2 的所有值
    public List<Object> between(int key1, int key2) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                BSTNode pop = stack.pop();
                if (pop.key >= key1 && pop.key <= key2) {
                    result.add(pop.value);
                } else if (pop.key > key2) {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }
}
